import java.util.*;

public class BinaryTree {

    static class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public char val;

        public TreeNode(char val) {
            this.val = val;
        }
    }


    public TreeNode root;

    public void create() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        root = A;
    }

    public List<List<TreeNode>> levelOrder1(TreeNode root) {
        List<List<TreeNode>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<TreeNode> tmp = new ArrayList<>();
            while(size != 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }

    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val);
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    public List<List<TreeNode>> levelOrder2(TreeNode root) {
        List<List<TreeNode>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<TreeNode> tmp = new ArrayList<>();
            while( size != 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }


    //给定一个前序遍历的字符串创建二叉树
    public static int i = 0;
    public static TreeNode create(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = create(str);
            root.right = create(str);
        }else {
            i++;
        }
        return root;
    }


    /**
     * 最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //先判断根节点是不是节点中的任意一个
        if (root == p || root == q) {
            return root;
        }
        //遍历判断是否在左树
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        //遍历判断是不是在右树
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        if (left != null && right != null) {
            return root;
        }else if(left != null) {
            return left;
        }else if(right != null) {
            return right;
        }else {
            return null;
        }
    }

    /**
     * 获取从根节点到指定节点路径上的所有节点
     * @param root
     * @param node
     * @param stack
     * @return
     */
    public boolean getPath(TreeNode root, TreeNode node,
                           Deque<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean ret1 = getPath(root.left,node,stack);
        if (ret1) {
            return true;
        }
        boolean ret2 = getPath(root.right,node,stack);
        if (ret2) {
            return true;
        }
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        int size = Math.abs(size1 - size2);
        while(size != 0) {
            if (size1 > size2) {
                stack1.pop();
            }else{
                stack2.pop();
            }
            size--;
        }

        while(!stack1.isEmpty()) {
            TreeNode cur1 = stack1.pop();
            TreeNode cur2 = stack2.pop();
            if (cur1 == cur2) {
                return cur1;
            }
        }
        return null;

    }

//    public TreeNode buildTree(int[] preOrder,int[] inorder) {
//        TreeNode root = bulidTreeChild(preOrder,inorder,0,preOrder.length - 1);
//        return root;
//    }
//
//    public TreeNode bulidTreeChild(int[] preOrder,int[] inOrder,int ib,int ie) {
//        if (ib > ie) {
//            return null;
//        }
//        TreeNode root = new TreeNode(preOrder[i]);
//        //找到根在中序遍历的位置
//        int rootIndex = findIndex(inOrder,ib,ie,preOrder[i]);
//        i++;
//        root.left = bulidTreeChild(preOrder,inOrder,,ib,rootIndex - 1);
//        root.right = bulidTreeChild(preOrder,inOrder,rootIndex + 1,ie);
//        return root;
//    }
//
//    private int findIndex(int[] inOrder,int ib,int ie,int key) {
//        for (int j = ib; j <= ie; j++) {
//            if (inOrder[j] == key) {
//                return j;
//            }
//        }
//        return -1;
//    }
//
//    int j ;
//    public TreeNode buildTreeChild1(int[] inorder,int[] postorder,int begin,int end) {
//        if (begin > end) {
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[j]);
//        int rootIndex = findIndex1(inorder,begin,end,postorder[j]);
//        j--;
//        //先创建右树，再创建左树
//        root.right = buildTreeChild1(inorder,postorder,rootIndex + 1,end);
//        root.left = buildTreeChild1(inorder,postorder,begin,rootIndex - 1);
//        return root;
//    }
//
//    public int findIndex1(int[] inorder,int begin,int end,int key) {
//        for (int k = begin; k <= end ; k++) {
//            if (inorder[k] == key) {
//                return k;
//            }
//        }
//        return -1;
//    }



    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        tree2strChild(root,sb);
        return sb.toString();
    }

    public void tree2strChild(TreeNode root,StringBuilder str) {
        if(root == null) {
            return;
        }
        str.append(root.val);
        if(root.left != null) {
            str.append("(");
            tree2strChild(root.left,str);
            str.append(")");
        }else {
            if(root.right != null) {
                str.append("()");
            }else {
                return;
            }
        }

        if(root.right == null) {
            return;
        }else {
            str.append("(");
            tree2strChild(root.right,str);
            str.append(")");
        }
    }

    public void treeStr(TreeNode root,StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left != null) {
            stringBuilder.append("(");
            treeStr(root.left,stringBuilder);
            stringBuilder.append(")");
        }else {
            if (root.right == null) {
                return;
            }else {
                stringBuilder.append("()");
            }
        }

        if (root.right != null) {
            stringBuilder.append("(");
            treeStr(root.right,stringBuilder);
            stringBuilder.append(")");
        }else {
            return;
        }
    }

    public void treeStr1(TreeNode root,StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);
        if (root.left == null && root.right == null) {
            return;
        } else if (root.left == null && root.right != null) {
            stringBuilder.append("()");
            stringBuilder.append("(");
            treeStr1(root.right,stringBuilder);
            stringBuilder.append(")");
        } else if (root.left != null && root.right == null) {
            stringBuilder.append("(");
            treeStr1(root.left,stringBuilder);
            stringBuilder.append(")");
        } else {
            stringBuilder.append("(");
            treeStr1(root.left,stringBuilder);
            stringBuilder.append(")");
            stringBuilder.append("(");
            treeStr1(root.right,stringBuilder);
            stringBuilder.append(")");
        }
    }


    /**
     * 判断一棵树是不是完全二叉树
     * @param root
     * @return
     */
    public boolean isCompleteTree(TreeNode root) {
        //层次遍历二叉树
        if (root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(root.left);
                queue.offer(root.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if (tmp != null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 非递归前序遍历
     * @param root
     */
    public void preOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode top = root;
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while  (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                System.out.print(cur.val);
                cur = cur.left;

            }
            top = stack.pop();
            cur = top.right;
        }
    }

    public void inOrderNor(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode top = root;
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while  (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;

            }
            top = stack.pop();
            System.out.print(top.val);
            cur = top.right;
        }
    }


    public void inOrderNor1(TreeNode root) {
        if (root == null) {
            return;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode top = root;
        while (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            System.out.print(top.val);
            cur = top.right;
        }
    }

    public void postOrder(TreeNode root) {

    }












}
